package com.ctliu.datastructure.priorityqueue;

import com.ctliu.datastructure.linkedlist.ListNode;

/**
 * <b>小顶堆</b>
 */
public class MinHeap {

    /*
              min
        1->4->5->null
        1->3->4->null
        2->6->null

        小顶堆
            1 2 4
        新链表
            s->1
     */

    ListNode[] array;
    int size;

    public MinHeap(int capacity) {
        array = new ListNode[capacity];
    }

//    入队
    public boolean offer(ListNode offered) {
        if (isFull()) {
//            元素满,操作失败
            return false;
        }
//        入队节点位置计算,同时队列长度+1
        int child = size++;
//        计算父节点位置
        int parent = (child - 1) / 2;
        while (child > 0 && offered.val < array[parent].val) {
//            如果子节点不是根节点,并且父节点比子节点大,则需要维护堆(维护成小顶堆)
//            父节点下沉
            array[child] = array[parent];
//            子节点上浮
            child = parent;
//            计算新的父节点索引
            parent = (child - 1) / 2;
        }
//        退出循环:满足小顶堆
//        赋值
        array[child] = offered;
        return true;
    }

//    出队
    public ListNode poll() {
        if (isEmpty()) {
//            元素空,出队失败
            return null;
        }
//        首尾交换
        swap(0, size - 1);
//        队列长度-1
        size--;
        ListNode e = array[size];
        array[size] = null; // help GC

        // 下潜
        down(0);

        return e;
    }

//    下潜操作
    private void down(int parent) {
//        计算左孩子索引
        int left = 2 * parent + 1;
//        右孩子索引
        int right = left + 1;
        int min = parent; // 假设父元素最小
//        比较,并交换最小值(索引)
        if (left < size && array[left].val < array[min].val) {
            min = left;
        }
//        比较并交换最小值(索引)
        if (right < size && array[right].val < array[min].val) {
            min = right;
        }
        if (min != parent) { // 有孩子比父亲小
            swap(min, parent);
//            递归,继续下潜
            down(min);
        }
    }

//    交换
    private void swap(int i, int j) {
        ListNode t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

//    判空
    public boolean isEmpty() {
        return size == 0;
    }
//    判满
    public boolean isFull() {
        return size == array.length;
    }
}
